def calculateMinimumHP(dungeon) -> int:
    """
    计算并返回勇士从地牢左上角到右下角所需的最小生命值。

    该函数通过动态规划解决问题，考虑到勇士的生命值不能小于1。

    :param dungeon: 二维列表，表示地牢的布局，其中每个元素代表该位置的伤害值。
    :return: 勇士所需的最小生命值。
    """
    # 获取地牢的行数和列数
    n, m = len(dungeon), len(dungeon[0])
    # 定义一个足够大的数，用于初始化DP表格的边界值
    BIG = 10 ** 9
    # 初始化动态规划表格，多出的一行一列用于简化边界条件的处理
    dp = [[BIG] * (m + 1) for _ in range(n + 1)]
    # 设置边界条件，确保勇士到达公主所在地的生命值至少为1
    dp[n][m - 1] = dp[n - 1][m] = 1
    # 从右下角向左上角遍历，计算到达每个格子所需的最小生命值
    for i in range(n - 1, -1, -1):
        for j in range(m - 1, -1, -1):
            # 计算从下方和右方传来的最小生命值
            minn = min(dp[i + 1][j], dp[i][j + 1])
            # 确保勇士的生命值至少为1，同时考虑当前格子的伤害值
            dp[i][j] = max(minn - dungeon[i][j], 1)
    # 返回到达地牢左上角所需的最小生命值
    return dp[0][0]


def start():
    dungeon = [[-2, -3, 3], [-5, -10, 1], [10, 30, -5]]
    print(calculateMinimumHP(dungeon))


if __name__ == '__main__':
    start()
